package array;

/**
 * Complexity of this program is O(n^2)
 * 
 * Please note that O(n * log n) algorithm also exists
 * */
public class LongestIncreasingSubsequence {

	private static int SubsequenceLength(int[] arr)
	{
		int len = arr.length; // length of given array
		int[] auxArray = new int[len]; // auxilary array to maintain max len of LIS

		//initialize
		for(int index = 0; index < auxArray.length; index++){
			auxArray[index] = 1; // each element is at least at the end of LIS of length 1
		}

		int int_max = 0; // variable to maintain max len of LIS
		int int_max_index = 0; // index of element who is at the end of LIS

		//fill auxArray containing the length of the LIS.
		//keep track of the longest LIS with int_max / int_max_index.
		for (int i = 1; i < len; i++){

			for (int j = 0; j < i; j++){
				// second condition preserves the max length found so far e.g. if array[i] is 3 and
				// array[j] is 1 then current max length (2) of LIS is lesser than already found 
				// LIS of 3, so no need to consider it
				if( (arr[i] > arr[j] && (auxArray[i] < auxArray[j] + 1) )) 
					auxArray[i] = auxArray[j] + 1; // LIS length got increment by one

			}//end j

			if (auxArray[i] > int_max){
				int_max = auxArray[i];
				int_max_index = i;				
			}

		} //end i


		// constructing the LIS array
		int k = int_max;
		int[] lis = new int[int_max]; // LIS array
		int currNum = 0;
		int prevNum = k + 1;

		for(int i = int_max_index; i >= 0; i--){
			currNum = auxArray[i];
			if(currNum == prevNum - 1){
				lis[--k] = arr[i];
				prevNum = currNum;
			}
		}

		//print the LIS 
		System.out.print("[");
		for (int i = 0; i < lis.length; i++) {
			System.out.print( lis[i] +" ");
		}
		System.out.println("]");

		return int_max; //return length of LIS
	} //end method


	public static void main(String[] args){
		int[ ] Seq1 = {9,5,2,8,7,3,1,6,4};
		int[ ] Seq2= {11, 17, 5, 8, 6, 4, 7, 12, 3};
		int[ ] Seq3= {7, 22, 9, 8, 21, 50, 41, 60 , 30};

		System.out.println("length - " + SubsequenceLength(Seq1));
		System.out.println("length - " + SubsequenceLength(Seq2));
		System.out.println("length - " + SubsequenceLength(Seq3));
	}//end main
}
